import java.util.Arrays;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-01-15
 * Time: 18:10
 */
public class Solution2 {
    //思路：
   // 1.整体异或,得知最后的结果肯定在某一二进制位上,有不同的数
    //2.就利用这个性质去找到这个二进制位,怎么找呢？利用flag=1不断左移的值按位与最终结果,只要按位与之后的结果不为0,说明这个位就是我们要找的二进制位
    //3.找到这个为1的位之后,那么就反过来去求这两个数,利用flag当前位为1,去按位与数组的每一个数字,那么就可以把数字分成两组了,然后再让他们与给定的num1和num2异或，最终得到两个不同的数
    public static int[] FindNumsAppearOnce (int[] array) {
        if(array == null ){
            return null;
        }
        //给定一个变量用于异或整体
        int ret=array[0];
        int num1=0;
        int num2=0;
        for(int i=1;i<array.length; i++){
            ret^=array[i];
        }
        //这个结果一定不为0，找到这个数的二进制位为1的位置，按照从高位到低位的顺序查找
        int size=Integer.SIZE;//32个比特位
        int flag=1;
        while(size>0){
            size-=1;//左移
            //如果flag左移后跟ret按位与的结果不为0，说明当前二进制位是1
            if(((flag<<size) & ret)!=0){
                flag<<=size;
                break;//找到了这个位置，退出
            }
        }
        //然后根据当前位是0还是1的情况分组
        for(int i=0;i<array.length; i++){
            //array中肯定有一一些数是当前二进制位不是1的，那么他们与flag当前位的1按位与就是0了，即使有多个数，但是相同的数只要异或就是0
            if((flag&array[i])==0){
                //可以用参数传回结果
                num1^=array[i];//只剩下最后一个当前二进制位是0，但是是出现一次的数字
            }else{
                //当前二进制位是1，那么按位与的结果就不是0，那么最后异或的结果就是另一个出现一次的数字
                num2^=array[i];
            }
        }
        return new int[] {num1, num2};
    }

    public static void main(String[] args) {
        int[] array = {1,1,2,2,3,3,4,5};
        System.out.println(Arrays.toString(FindNumsAppearOnce(array)));
    }

}
